package leetcode_1801_1900;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.TreeMap;
import java.util.TreeSet;

public class LeeCode_1871 {
    public static void main(String[] args) {
        System.out.println(canReach("00111010", 3, 5));
//        System.out.println(canReach("00", 1, 1));
    }
    private static boolean canReach(String s, int minJump, int maxJump) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        if (cs[0] == '1' || cs[n - 1] == '1')
            return false;
        Deque<Integer> deque = new ArrayDeque<>();
        boolean[] dp = new boolean[n];
        dp[0] = true;
        deque.add(0);
        int have = minJump - 1;
        while (!deque.isEmpty()){
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                Integer p = deque.pop();
                int r = Math.min(n - 1, p + maxJump);
                for (int j = Math.max(have + 1, p + minJump); j <= r; j++) {
                    if (cs[j] == '0') {
                        dp[j] = true;
                        deque.offer(j);
                    }
                }
                have = r;
            }
        }
        return dp[n - 1];
    }
}